#include <stdio.h>
#define kMaxSize 20

// 求该函数的事件复杂度 O(n)
//void function(){
//  for(int i=1;i<n;i*=2){
//    for(int j=0;j<i;j++){
//      sum++;
//    }
//  }
//}
/* A.O(logn) B.O(n) C.O(nlogn) D(n^2) */

/**
 * 先实现功能，再来重构
 * 后缀表达式和前缀表达式都是没有括号的
 * 表达式的运算都是先转成后缀没有括号后再进行计算的。
 *  
 **/
 /**
  * 表达式求值的算法思想
  * 取出的是数字直接加入后缀表达式
  * 取出的是运算符则分情况判断
  *	  ‘（’ 入栈
  *	  ‘）’ 则依次把栈中的运算符加入到后缀表达式中，直到出现‘（’并删除栈中‘（’
  *   若为运算符号 ‘+’，‘-’，‘*’，‘/’
  *		栈空，入栈；
  *		栈顶元素为（ 入栈；
  *		高于栈顶元素优先级，入栈
  *		否则，依次弹出栈顶运算符，直到一个优先级比他低的运算符或‘（’为止
  * 遍历完成，弱栈非空依次弹出所有元素。
  */
//
///*栈的数据结构*/
//typedef struct
//{
//    char data[kMaxSize];
//    int top;
//} YKStack;
//typedef struct
//{
//    int data[kMaxSize];
//    int top;
//} YIStack;
////初始化
//int InitStack(YKStack *yks);
//
///**判断栈是否为空
// * int 为错误代码
//*/
//int StatckEmpty(YKStack yks);
//int Push(YKStack *yks, char e);
//int Pop(YKStack *yks, char *e);
//int GetTop(YKStack yks, char *e);
//
///*校验一个表达式是否合法*/
//int checkExpression(char *str);
//int checkMathExpression(char *str);
//int intFromStack(YKStack *ts);
//
//int tmain()
//{
//    printf("Hello World！ It begin 0.0\n");
//    /**TODO
//*
//*/
//    //    char *str = "()[]";
//    //    int r = checkExpression(str);
//    //    printf("re = %d", r);
//    YKStack yks;
//    // yks.top = 3;
//    InitStack(&yks);
//    Push(&yks, '3');
//    // Push(&yks, '+');
//    Push(&yks, '4');
//    // Push(&yks, '=');
//    Push(&yks, '7');
//    printf("yks.top = %d\n", yks.top);
//
//    int da = intFromStack(&yks);
//    printf("yks.v = %d\n", da);
//
//    char *str = "3*(5+2)";
//    int s = checkMathExpression(str);
//    printf("str status = %d", s);
//    // char a, b;
//    // Pop(&yks, &a);
//    // GetTop(yks, &b);
//    // printf("pop->%c, top-> %c\n", a, b);
//    return 0;
//}
//int intFromStack(YKStack *ts)
//{
//    int v = 0;
//    int a = 1;
//    char c;
//    for (int i = ts->top; i >= 0; i--)
//    {
//        Pop(ts, &c);
//        v += ((int)c - 48) * a;
//        a *= 10;
//    }
//    return v;
//}
//int checkMathExpression(char *str)
//{
//    YKStack cs, ts; // 运算符栈，数值暂存栈
//    YIStack ds;     // 数值栈
//    char c = str[0];
//    int a = (int)c;
//    if (a < 48 || a > 57)
//    {
//        //数学表达式需要以数字开头
//        return 1;
//    }
//    int i = 0, j = 0;
//    while (c)
//    {
//        printf("c = %c", c);
//        if (c == '(')
//        {
//            j++;
//        }
//        else if (c == ')')
//        {
//            j--;
//        }
//        else
//        {
//            c = str[++i];
//        }
//    }
//    // 以）结尾
//    c = str[--i];
//    a = (int)c;
//    if (a == 41 && j == 0)
//    {
//        return 0;
//    }
//    // 以数字结尾
//    if (a >= 48 && a <= 57)
//    {
//        return 0;
//    }
//    else
//    {
//        // 表达式结尾不正确
//        return 2;
//    }
//}
//
//int InitStack(YKStack *yks)
//{
//    yks->top = -1;
//    return 0;
//}
//
//int StatckEmpty(YKStack yks)
//{
//    if (yks.top == -1) // 栈空
//    {
//        return 0;
//    }
//    else
//    { // 不空
//        return 1;
//    }
//}
//
//int Push(YKStack *yks, char e)
//{
//    if (yks->top == kMaxSize - 1) // 栈满，无法再添加
//    {
//        return 1;
//    }
//
//    // yks->top++;
//    // yks->data[yks->top] = e;
//    yks->data[++yks->top] = e;
//    return 0;
//}
//int Pop(YKStack *yks, char *e)
//{
//    if (yks->top == -1) // 栈空，无法弹出
//    {
//        return 1;
//    }
//
//    // *e = yks->data[yks->top];
//    // yks->top--;
//    *e = yks->data[yks->top--];
//
//    return 0;
//}
//int GetTop(YKStack yks, char *e)
//{
//    if (yks.top == -1)
//    {
//        return 1;
//    }
//
//    *e = yks.data[yks.top];
//    return 0;
//}
//
//int checkExpression(char *str)
//{
//    YKStack yks;
//    InitStack(&yks);
//    int i = 0;
//    char c;
//    // Push(&yks, str[0]);
//    // i++;
//    while (str[i])
//    {
//        int f = GetTop(yks, &c);
//        if (f)
//        {
//            Push(&yks, str[i++]);
//            continue;
//        }
//
//        if (c == '(' && str[i] == ')')
//        {
//            Pop(&yks, &c);
//            i++;
//            continue;
//        }
//        else if (c == '[' && str[i] == ']')
//        {
//            Pop(&yks, &c);
//            i++;
//            continue;
//        }
//        else
//        {
//            Push(&yks, str[i++]);
//            continue;
//        }
//    }
//    return yks.top == -1 ? 0 : 1;
//}
